1. Field of the Invention
This invention relates to a method and apparatus for managing a list structure and, more particularly, to extensions to the architecture of a list processor that render it especially suitable for processing shared message queues.
2. Description of the Related Art
IBM's MQSeries® is a set of middleware products that allow user applications to intercommunicate using messages, without having to know the complexities of the underlying hardware and software platform. Applications communicate using the MQSeries application programming interface (API), issuing such calls as MQPUT to put a message onto a queue and MQGET to get a message from a queue. MQSeries is described in such publications as MQSeries Planning Guide, IBM GC33-1349-07 (January 1999), incorporated herein by reference.
The IBM S/390® Parallel Sysplex® configuration is a cluster of interconnected processing nodes with attachments to shared storage devices, network controllers, and core cluster technology components, consisting of coupling facilities, coupling support facilities, and external time references (ETRs). A coupling facility (CF) enables high-performance read/write sharing of data by applications running on each node of the cluster through global locking and cache coherency management mechanisms. It also provides cluster-wide queuing mechanisms for workload distribution and message passing between nodes.
The coupling facility is described in the following patents and publications, incorporated herein by reference:                “In a Multiprocessing System Having a Coupling Facility, Communicating Messages Between the Processors and the Coupling Facility in Either a Synchronous Operation or an Asynchronous Operation”, by D. A. Elko et al., Ser. No. 08/420,893, Filed Apr. 11, 1995, now U.S. Pat. No. 5,561,809;        “Sysplex Shared Data Coherency Method And Means”, by D. A. Elko et al., Ser. No. 07/860,805, Filed Mar. 30, 1992, now U.S. Pat. No. 5,537,574;        “Method And Apparatus For Distributed Locking Of Shared Data, Employing A Central Coupling Facility”, by D. A. Elko et al., Ser. No. 07/860,808, Filed Mar. 30, 1992, now U.S. Pat. No. 5,339,427;        “Command Quiesce Function”, by D. A. Elko et al., Ser. No. 07/860,330, Filed Mar. 30, 1992, now U.S. Pat. No. 5,339,405;        “Software Cache Management Of A Shared Electronic Store In A Sysplex”, by D. A. Elko et al., Ser. No. 07/860,807, Filed Mar. 30, 1992, now U.S. Pat. No. 5,457,793;        “Multiple Processor System Having Software For Selecting Shared Cache Entries Of An Associated Castout Class For Transfer To A DASD With One I/O Operation”, by D. A. Elko et al, Ser. No. 07/860,806, Filed Mar. 30, 1992, now U.S. Pat. No. 5,493,668;        “Command Execution System For Using First And Second Commands To Reserve And Store Second Command Related Status Information In Memory Portion Respectively”, by D. A. Elko et al., Ser. No. 07/860,378, Filed Mar. 30, 1992, now U.S. Pat. No. 5,392,397;        “Integrity Of Data Objects Used To Maintain State Information For Shared Data At A Local Complex”, by D. A. Elko et al, Ser. No. 07/860,800, Filed Mar. 30, 1992, now U.S. Pat. No. 5,331,673;        “Management Of Data Objects Used To Maintain State Information For Shared Data At A Local Complex”, by J. A. Frey et al, Ser. No. 07/860,797, Filed Mar. 30, 1992, now U.S. Pat. No. 5,388,266;        “Clearing Data Objects Used To Maintain State Information For Shared Data At A Local Complex When At Least One Message Path To The Local Complex Cannot Be Recovered”, by J. A. Frey et al., Ser. No. 07/860,647, Filed Mar. 30, 1992, now U.S. Pat. No. 5,394,542;        “Coupling Facility For Receiving Commands From Plurality Of Hosts For Activating Selected Connection Paths To I/O Devices And Maintaining Status Thereof”, by D. A. Elko. et al., Ser. No. 08/324,447, Filed Oct. 18, 1994, now U.S. Pat. No. 5,463,736;        “Data Processing System And Method For Providing Notification In A Central Processor Of State Changes For Shared Data Structure On External Storage”, by J. A. Frey et al., Ser. No. 07/860,809, Filed Mar. 30, 1992, now U.S. Pat. No. 5,390,328;        “Method And Apparatus For Performing Conditional Operations On Externally Shared Data”, by J. A. Frey et al., Ser. No. 08/383,532, Filed Feb. 1, 1995, now U.S. Pat. No. 5,742,830;        “Apparatus And Method For List Management In A Coupled Data Processing System”, by J. A. Frey et al., Ser. No. 07/860,633, Filed Mar. 30, 1992, now U.S. Pat. No. 5,410,695;        “Interdicting I/O And Messaging Operations In A Multi-System Complex”, by D. A. Elko et al., Ser. No. 07/860,489, Filed Mar. 30, 1992, now U.S. Pat. No. 5,394,554;        “Method And Apparatus For Coupling Data Processing Systems”, by D. A. Elko et al., Ser. No. 07/860,803, Filed Mar. 30, 1992, now U.S. Pat. No. 5,317,739;        “Authorization Method For Conditional Command Execution”, by D. A. Elko et al., Ser. No. 08/408,446, Filed Mar. 22, 1995, now U.S. Pat. No. 5,450,590;        “Dynamically As signing a Dump Space in a Shared Data Facility to Receive Dumping Information to be Captured”, by D. A. Elko et al., Ser. No. 08/471,895, Filed Jun. 7, 1995, now U.S. Pat. No. 5,664,155;        “Method And System For Capturing and Controlling Access To Information In A Coupling Facility”, by D. E. Neuhard et al., Ser. No. 08/146,647, filed Nov. 1, 1993, now U.S. Pat. No. 5,630,050;        “Method and System for Determining and Overriding Information Unavailability Time at a Coupling Facility”, by D. A. Neuhard et al., Serial. No. 08/779,196, filed Jan. 6, 1997, now U.S. Pat. No. 5,875,484;        “Requesting a Dump of Information Stored within a Coupling Facility, in Which the Dump Includes Serviceability Information from an Operating System That Lost Communication with the Coupling Facility”, by D. A. Neuhard et al., Serial. No. 08/779,195, filed Jan. 6, 1997, now U.S. Pat. No. 5,860,115;        “Method and Apparatus for Expansion, Contraction, and Reapportionment of Structured External Storage Structures”, by D. J. Dahlen et al., Ser. No. 08/304,458, filed Sep. 12, 1994, now U.S. Pat. No. 5,581,737;        “Method of Managing Resources in One or More Coupling Facilities Coupled to One or More Operating Systems in One or More Central Programming Complexes Using a Policy”, by R. A. Allen et al., Ser. No. 08/607,053, filed Feb. 26, 1996, now U.S. Pat. No. 5,634,072;        “Method and System for Managing Data and Users of Data in a Data Processing System”, by R. A. Allen, Ser. No. 08/146,727, filed Nov. 1, 1993, now U.S. Pat. No. 5,465,359;        “Method and System for Reconfiguring a Storage Structure Within a Structure Processing Facility”, by R. A. Allen et al., Ser. No. 08/544,941, filed Oct. 18, 1995, now U.S. Pat. No. 5,515,499;        “Method for Coordinating Executing Programs in a Data Processing System”, by R. A. Allen et al., Ser. No. 08/439,269, filed May 9, 1995, now U.S. Pat. No. 5,604,863;        “Coherence Controls for Store-Multiple Shared Data Coordinated by Cache Directory Entries in a Shared Electronic Storage”, by K. S. Carpenter et al., Ser. No. 08/148,707, filed Nov. 8, 1993, now U.S. Pat. No. 5,544,345;        “Method and System for Log Management in a Coupled Data Processing System”, by R. V. Geiner et al., Ser. No. 08/632,683, filed Apr. 15, 1996, now U.S. Pat. No. 5,737,600; and        J. M. Nick et al., “S/390 cluster technology: Parallel Sysplex”, IBM Systems Journal, vol. 36, no. 2, 1997, pages 172-201.        
It would be desirable to be able to use the list-processing capabilities of the coupling facility to implement a message queue that is shared by queue managers residing on different systems across a sysplex. To be suitable for this purpose, the CF list architecture should allow MQSeries to efficiently implement the following message-queuing semantics:    1. A message must be uniquely identified.    2. A message put cannot be visible to other units of work (UOWs) until it is committed.            When a message is written by a UOW, it must not be visible to other units of work anywhere in the queue-sharing group (QSG) until the message is committed. The uncommitted message however is available to the unit of work that wrote it.            3. Committed messages must be maintained in proper sequence.            Committed messages eligible to be read must be in priority sequence, from highest priority to lowest priority. If there are multiple messages with the same priority, then the set of messages must be maintained in order of arrival sequence within designated priority.            4. Messages read must be unavailable to others UOWs in the QSG.            When a committed message is read by a unit of work, then no other unit of work anywhere in the queue-sharing group can read the same message. If the message that is read is committed, it must be deleted from the CF list structure so that it is never visible again to another unit of work.            5. Messages read that are backed out must be reinserted into their proper committed positions with respect to both priority and time of arrival.            If the message that was read is backed out, it must again become visible to other units of work executing in the queue-sharing group. When the message is backed out, it must be reinserted into the committed portion of a list with respect to both its priority and its time of arrival (when the message was originally put).            6. Committing and aborting messages for a UOW must be efficient.